#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
//
#include <algorithm>
#include <string>
#include <iomanip>
#define MAX 1000
typedef struct {
    int weight;
    int parent, lchild, rchild;
}*HuffmanTree, HTNode;

string str, huffmancode1, huffmancode2, dehuffmancode1, dehuffmancode2;
int y;

void menu()
{
    cout << " **************************************\n\n";
    cout << "    基于哈夫曼树的数据压缩算法：\n\n";
    cout << "    1.输入字符串构造哈夫曼树\n";
    cout << "    2.输入二进制编码进行解码\n";
    cout << "    0.退出\n\n";
    cout << " **************************************\n\n";
}
void CountNumber(string s, int& k, pair<char, int>ch[])///统计字符出现频率
{
    int Number = 1;
    sort(s.begin(), s.end());
    for (int i = 0; i < s.size(); i++) {
        if (s[i] != s[i + 1]) {
            ch[++k] = make_pair(s[i], Number);
            Number = 1;
        }
        else Number++;
    }
}
void Select(HuffmanTree HT, int t, int& s1, int& s2)/// 从当前森林中选择双亲为0且权值最小的两个树根结点s1和s2
{
    int MIN1 = 0x3f3f3f3f, MIN2 = 0x3f3f3f3f;//MIN1最小值，MIN2次小值
    for (int i = 1; i <= t; i++) {
        if (!HT[i].parent && HT[i].weight < MIN1) {
            MIN2 = MIN1;
            s2 = s1;
            MIN1 = HT[i].weight;
            s1 = i;
        }
        else if (!HT[i].parent && HT[i].weight < MIN2) {
            MIN2 = HT[i].weight;
            s2 = i;
        }
    }
}
void CreatHuffmanTree(HuffmanTree& HT, int n, pair<char, int>ch[])///构造哈夫曼树
{
    if (n <= 1)return;
    int m = 2 * n - 1;
    HT = new HTNode[m + 1];
    for (int i = 1; i <= m; i++)
        HT[i].parent = 0, HT[i].lchild = 0, HT[i].rchild = 0;
    for (int i = 1; i <= n; i++)
        HT[i].weight = ch[i].second;

    int s1, s2;
    for (int i = n + 1; i <= m; i++) {
        Select(HT, i - 1, s1, s2);
        HT[s1].parent = i, HT[s2].parent = i;
        HT[i].lchild = s1, HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}
void CreatHuffmanCode(HuffmanTree HT, char**& HC, int n, pair<char, int>ch[])///求各个字符的哈夫曼编码，数组HC存储
{
    char* cd;
    HC = new char* [n + 1];
    cd = new char[n];
    cd[n - 1] = '\0';
    for (int i = 1; i <= n; i++) {
        int sta = n - 1, c = i, f = HT[i].parent;
        while (f) {
            --sta;//倒序存储
            if (HT[f].lchild == c)
                cd[sta] = '0';
            else
                cd[sta] = '1';
            c = f; f = HT[f].parent;//继续向上回溯
        }
        HC[i] = new char[n - sta];
        strcpy(HC[i], &cd[sta]);
    }
    delete cd;
}
void HuffmanCodeString(char* HC[], pair<char, int>ch[], int n, string str)///求进行哈夫曼编码后的字符串，编码字符串huffmancode存储
{
    huffmancode1 = "";
    for (int i = 0; i < str.size(); i++) {//依次遍历字符串的每个字符
        for (int j = 1; j <= n; j++) {
            if (str[i] == ch[j].first) {//每个字符找到它对应的编码
                huffmancode1 += HC[j];
                break;
            }
        }
    }
}
void Dehuffmancode1(HuffmanTree HT, int n, pair<char, int>ch[])///求对编码进行解码后的字符串，解码字符串dehuffmancode1存储
{
    dehuffmancode1 = "";
    int m = 2 * n - 1;
    int k = m;
    for (int i = 0; i < huffmancode1.size(); i++) {
        if (huffmancode1[i] == '0')//0找左儿子
            k = HT[k].lchild;
        else if (huffmancode1[i] == '1')//1找右儿子
            k = HT[k].rchild;
        if (k <= n) {
            dehuffmancode1 += ch[k].first;
            k = m;//重新从根开始
        }
    }
}
bool Dehuffmancode2(HuffmanTree HT, int n, pair<char, int>ch[])///输入二进制编码后根据已有的哈夫曼树解码
{
    cout << "请输入二进制编码：";
    cin >> huffmancode1;
    for (int i = 0; i < huffmancode1.size(); i++) {
        if (huffmancode1[i] != '0' && huffmancode1[i] != '1') {
            cout << "该二进制编码不符合标准!\n";
            return false;
        }
    }
    Dehuffmancode1(HT, n, ch);
    return true;
}
void Inputstring(int& n, HuffmanTree& HT, char**& HC, pair<char, int>ch[])///输入字符串
{
    system("cls");
    menu();
    cout << " **************************************"<<endl;
    cout << "请输入字符串：";
    getchar();
    getline(cin, str);
    CountNumber(str, n, ch);
    if (n == 1) {
        y = 0;
        cout << "\n该字符串存在问题，请重新输入！\n";
        return;
    }
    CreatHuffmanTree(HT, n, ch);
    CreatHuffmanCode(HT, HC, n, ch);
    HuffmanCodeString(HC, ch, n, str);
    huffmancode2 = "";
    huffmancode2 = huffmancode1;
    Dehuffmancode1(HT, n, ch);
    dehuffmancode2 = "";
    dehuffmancode2 = dehuffmancode1;
    cout << "\n构造哈夫曼树成功！\n"; y = 1;
}
int main()
{
    menu();
    HuffmanTree HT = 0;
    char** HC = 0;
    int choose = -1, n;
    pair<char, int>ch[MAX];
    while (choose)
    {
        cout << "\n请选择功能：";
        cin >> choose;
        if (!y && choose != 1 && choose != 0)
        {
            cout << endl;
            cout << " **************************************" << endl;
            cout << "请先执行指令1，输入一个字符串！\n";
            cout << " **************************************" << endl;
            continue;
        }
        cout << endl; 
        switch (choose)
        {
        case 0: cout << "退出成功！\n"; 
            break;
        case 1: n = 0; memset(ch, 0, sizeof(ch));
            Inputstring(n, HT, HC, ch);
            cout << "字符频率：";
            for (int i = 1; i <= n; i++)
                cout << ch[i].first << ":" << ch[i].second << ' ';
            cout << endl;
            cout << "哈夫曼编码为：";
            for (int i = 1; i <= n; i++)
                cout << ch[i].first << ":" << HC[i] << ' ';
            cout << endl;
            cout << " **************************************" << endl;
            break;
        case 2: if (Dehuffmancode2(HT, n, ch))
            cout << "该编码进行解码后的字符串为：" << dehuffmancode1 << endl;
            cout << " **************************************" << endl;
            break;
        default:cout << "指令不存在，请重新输入！\n";
            cout << " **************************************" << endl;
            break;
        }
    }
    return 0;
}